362. Design Hit Counter
Medium

Design a hit counter which counts the number of hits received in the past 5 minutes (i.e., the past 300 seconds).

Your system should accept a timestamp parameter (in seconds granularity), and you may assume that calls are being made to the system in chronological order (i.e., timestamp is monotonically increasing). Several hits may arrive roughly at the same time.

Implement the HitCounter class:

  • HitCounter() Initializes the object of the hit counter system.
  • void hit(int timestamp) Records a hit that happened at timestamp (in seconds). Several hits may happen at the same timestamp.
  • int getHits(int timestamp) Returns the number of hits in the past 5 minutes from timestamp (i.e., the past 300 seconds).

 

Example 1:

Input
["HitCounter", "hit", "hit", "hit", "getHits", "hit", "getHits", "getHits"]
[[], [1], [2], [3], [4], [300], [300], [301]]
Output
[null, null, null, null, 3, null, 4, 3]

Explanation
HitCounter hitCounter = new HitCounter();
hitCounter.hit(1);       // hit at timestamp 1.
hitCounter.hit(2);       // hit at timestamp 2.
hitCounter.hit(3);       // hit at timestamp 3.
hitCounter.getHits(4);   // get hits at timestamp 4, return 3.
hitCounter.hit(300);     // hit at timestamp 300.
hitCounter.getHits(300); // get hits at timestamp 300, return 4.
hitCounter.getHits(301); // get hits at timestamp 301, return 3.

 

Constraints:

  • 1 <= timestamp <= 2 * 109
  • All the calls are being made to the system in chronological order (i.e., timestamp is monotonically increasing).
  • At most 300 calls will be made to hit and getHits.

 

Follow up: What if the number of hits per second could be huge? Does your design scale?

Accepted
122.3K
Submissions
185.7K
Seen this question in a real interview before?
Companies
Related Topics
Similar Questions

Average Rating: 4.25 (16 votes)

Premium

Approach #1: Using Queue

Intuition

A key observation here is that all the timestamps that we will encounter are going to be in increasing order. Also as the timestamps' value increases we have to ignore the timestamps that occurred previously (having a difference of 300 or more with the latest timestamp). This is the case of considering the elements in the FIFO manner (First in first out) which is best solved by using the "queue" data structure.

Algorithm

We will add each timestamp to the queue in the hit method and will remove all the timestamps with difference greater than or equal to 300 from the queue inside getHits. The answer returned from the getHits method is then simply the size of the queue.

Below is the implementation of this approach.

Complexity Analysis

  • Time Complexity

    • hit - Since inserting a value in the queue takes place in O(1)O(1) time, hence hit method works in O(1)O(1).

    • getHits - Assuming a total of nn values present in the queue at a time and the total number of timestamps encountered throughout is NN. In the worst case scenario, we might end up removing all the entries from the queue in getHits method if the difference in timestamp is greater than or equal to 300. Hence in the worst case, a "single" call to the getHits method can take O(n)O(n) time. However, we must notice that each timestamp is processed only twice (first while adding the timestamp in the queue in hit method and second while removing the timestamp from the queue in the getHits method). Hence if the total number of timestamps encountered throughout is NN, the overall time taken by getHits method is O(N)O(N). This results in an amortized time complexity of O(1)O(1) for a single call to getHits method.

  • Space Complexity: Considering the total timestamps encountered throughout to be NN, the queue can have upto NN elements, hence overall space complexity of this approach is O(N)O(N).

Approach #2: Using Deque with Pairs

Consider the follow up, where we have multiple hits arriving at the "same" timestamps. We can optimize Approach 1 even further. In this approach, we'll not only keep the timestamps but will also keep the count of the timestamps as well. For example, if we call hit method 5 times for timestamp = 1, the queue in case of Approach 1 will look like [1, 1, 1, 1, 1]. This will lead to 5 removals in the getHits method when we remove the value 1 from the queue. To avoid this repetitive removals of the same value, in Approach 2, we'll store the value as (1, 5) where the first value 1 is the timestamp and the second value 5 is the count. For this, we'll use the "deque" data structure which allows us to insert and delete values from both the ends of the queue.

Algorithm

The updated algorithm in Approach 2 is as follows.

  • If we encounter the hit for the same timestamp, instead of appending a new entry in the deque, we simply increment the count of the latest timestamp.

  • In order to keep the track of total number of elements (for the last 300 seconds), we also use a variable total which we initialize to 0 and keep updating as we add or remove the elements from the queue. We increment the value of total by 1 when hit method is called and we decrement by the value of total by the count of the timestamp that we remove from the queue.

Below is the implementation of this approach.

Complexity Analysis

In the worst case, when there are not many repetitions, the time complexity and space complexity of Approach 2 is the same as Approach 1. However in case we have repetitions (say k repetitions of a particular ith timestamp), the time complexity and space complexities are as follows.

  • Time Complexity:

    • hit - O(1)O(1).

    • getHits - If there are a total of nn pairs present in the deque, worst case time complexity can be O(n)O(n). However, by clubbing all the timestamps with same value together, for the ith timestamp with k repetitions, the time complexity is O(1)O(1) as here, instead of removing all those k repetitions, we only remove a single entry from the deque.

  • Space complexity: If there are a total of NN elements that we encountered throughout, the space complexity is O(N)O(N) (similar to Approach 1). However, in the case of repetitions, the space required for storing those k values O(1)O(1).

Report Article Issue

Comments: 20
ambitechstrous's avatar
Read More

I did this without queues. Only maps.

def __init__(self):
    """
    Initialize your data structure here.
    """
    self.hits = {}
    

def hit(self, timestamp: int) -> None:
    """
    Record a hit.
    @param timestamp - The current timestamp (in seconds granularity).
    """
    if timestamp not in self.hits:
        self.hits[timestamp] = 0
    self.hits[timestamp] += 1
    

def getHits(self, timestamp: int) -> int:
    """
    Return the number of hits in the past 5 minutes.
    @param timestamp - The current timestamp (in seconds granularity).
    """
    begin = timestamp - 300
    hits_for_ts = 0
    for i in range(begin+1, timestamp+1):
        if i in self.hits:
            hits_for_ts += self.hits[i]
    return hits_for_ts

getHits is still constant time, as it is always looping 300 times (this is negligible when you have millions of timestamp). The proposed solution does similar stuff but seems overly complex

10
Show 5 replies
Reply
Share
Report
jargonsad's avatar
Read More

Deque solution approach #2 is not really optimized for space. You can reduce space complexity to O(1), since at any given time you need to keep at max 300 pairs. Solution is to also do pop while registering the hit and therefore maintaining a constant space complexity. Remember always popping is capped to 300 in both hit() and getHits() API.

5
Show 1 reply
Reply
Share
Report
cham_'s avatar
Read More

How come the official solution is not the most optimized one?

I posted a solution where hit function time complexity is O(1) and getHits func time complexity is O(log n) - https://leetcode.com/problems/design-hit-counter/discuss/1068290/C%2B%2B-w-full-explanation.-Beats-100-runtime.-hit-func-O(1)-and-getHits-func-O(logn)

2
Show 2 replies
Reply
Share
Report
abhishekrane121's avatar
Read More

This should be mark easy

1
Reply
Share
Report
milcars's avatar
Read More

Short c++ solution (20 lines).
Time complexity: hit O(1) ; getHits O(logN).
Space used O(n).
What do you think about it?

class HitCounter {
public:
    void hit(int timestamp) {
        hits.push_back(timestamp);

        // Prevent overloading.
        if (hits.front() < timestamp - 300)
            hits.pop_front();
    }

    int getHits(int timestamp) {
        auto it = upper_bound(hits.begin(), hits.end(), timestamp - 300);

        return hits.end() - it;
    }

private:
    deque<int> hits;
};

1
Reply
Share
Report
Endianless's avatar
1
Show 1 reply
Reply
Share
Report
ruzaikrgithub's avatar
Read More

Simple solution using map in Go which also accounts for concurrent hits.

type HitCounter struct {
	mu   sync.Mutex
	hits map[int]int
}

/** Initialize your data structure here. */
func Constructor() HitCounter {
	return HitCounter{
		hits: make(map[int]int),
	}
}

/** Record a hit.
  @param timestamp - The current timestamp (in seconds granularity). */
func (this *HitCounter) Hit(timestamp int) {
	this.mu.Lock()
	this.hits[timestamp] = this.hits[timestamp] + 1
	this.mu.Unlock()
}

/** Return the number of hits in the past 5 minutes.
  @param timestamp - The current timestamp (in seconds granularity). */
func (this *HitCounter) GetHits(timestamp int) int {
	this.mu.Lock()
	defer this.mu.Unlock()
	var start = timestamp - 299
	if start < 0 {
		start = 1
	}
	var noOfHits int
	for i := start; i <= timestamp; i++ {
		noOfHits = noOfHits + this.hits[i]
	}
	return noOfHits
}

1
Reply
Share
Report
fedrod's avatar
Read More

I believe there is an error in the C++ solution 2 -- It explains using a deque, but it does not, and in the hit() method it checks the .front() rather than the .back()

1
Show 1 reply
Reply
Share
Report
jada_vida's avatar
Read More

space complexity can be reduced to o(1)

0
Reply
Share
Report
satinMango's avatar
Read More

Java solution using Map

import java.util.Optional;

class HitCounter {

    private Map<Integer, Integer> hitMap;
    /** Initialize your data structure here. */
    public HitCounter() {
        hitMap = new HashMap<>();
    }
    
    /** Record a hit.
        @param timestamp - The current timestamp (in seconds granularity). */
    public void hit(int timestamp) {
        if(hitMap.containsKey(timestamp)) {
            hitMap.put(timestamp, hitMap.get(timestamp)+1);
        } else {
            hitMap.put(timestamp, 1);
        }
    }
    
    /** Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity). */
    public int getHits(int timestamp) {
        Optional<Integer> hits;
        
        if(timestamp <= 300) {
            // Find all the entries in the map from the range 1 to 300
             hits = hitMap.entrySet().stream()
                    .filter(e -> e.getKey() <= 300)
                    .map(Map.Entry::getValue)
                    .reduce(Integer::sum);
        } else {
            // Find all the entries in the map from the range timestamp to timestamp-300
            // timestamp-300
            hits = hitMap.entrySet().stream()
                    .filter(e -> e.getKey() > timestamp - 300)
                    .map(Map.Entry::getValue)
                    .reduce(Integer::sum);
        }
        if(hits.isPresent())
            return hits.get();
        else 
            return 0;
    }
}

0
Reply
Share
Report

You don't have any submissions yet.

/23
Contribute
|||
Saved
Trie
#208 Implement Trie (Prefix Tree)
Medium
#211 Design Add and Search Words Data Structure
Medium
#212 Word Search II
Hard
#336 Palindrome Pairs
Hard
#421 Maximum XOR of Two Numbers in an Array
Medium
#425 Word Squares
Hard
#472 Concatenated Words
Hard
#642 Design Search Autocomplete System
Hard
#648 Replace Words
Medium
#676 Implement Magic Dictionary
Medium
#677 Map Sum Pairs
Medium
#692 Top K Frequent Words
Medium
#720 Longest Word in Dictionary
Easy
#745 Prefix and Suffix Search
Hard
#1023 Camelcase Matching
Medium
#1032 Stream of Characters
Hard
#1065 Index Pairs of a String
Easy
#1638 Count Substrings That Differ by One Character
Medium
#1698 Number of Distinct Substrings in a String
Medium
#1707 Maximum XOR With an Element From Array
Hard
#1803 Count Pairs With XOR in a Range
Hard
#1804 Implement Trie II (Prefix Tree)
Medium
#1858 Longest Word With All Prefixes
Medium